Skúška Mareš 23.5.2025 (predtermín)
Prvé dve úlohy sú algoritmy a všetky dôkazy k nim potrebné, druhé dve sú príklady.
Mergesort
Silná súvislosť, silne súvislé komponenty
Máme gauč tvaru L (zaberá 3 zo 4 políčok 2x2 štvorca), štvorcovú sieť nxn a prekážky. Ak máme 2x2 štvorec s gaučom bez prekážky, tak vieme gauč ľubovoľne otočiť. Máme zadanú počiatočnú a cieľovú polohu, chceme nájsť čo najkratšiu cestu (na čo najmenej krokov).
Máme postupnosť dĺžky n (nezoradenú), chceme nájsť minimum všetkých k za sebou idúcich prvkov